Known cryptographic technologies include a common key cryptosystem and a public key cryptosystem.
In the common key cryptosystem, a message sender encrypts a message with a common key to obtain an encrypted message, and the receiver decrypts the encrypted message with the same common key to obtain the original message. Therefore, it is necessary to establish a procedure for the sender and receiver to possess the common key securely.
In the public key cryptosystem, (1) a receiver prepares a public key and a private key corresponding thereto, (2) a sender encrypts a message with the public key to obtain an encrypted message, and (3) the receiver decrypts the encrypted message with the private key to obtain the original message. Therefore, the sender needs to obtain the public key prepared by the receiver before encrypting the message. In other words, encryption is impossible unless the receiver generates the public key.
Predicate encryption has been proposed recently. In the predicate encryption, information X is embedded in an encrypted message during encryption by the sender, the receiver who has information Y having a specific relationship with the information X can decrypt the encrypted message or obtain information related to the message without knowing the message. The sender does not necessarily need to know the information Y possessed by the receiver during encryption. In addition, the sender does not necessarily need to determine the receiver before encryption. The sender can determine the information X actively, freely and with initiative. In theory, the information X is called an attribute I (variable) and the information Y is called a predicate f (propositional function or Boolean function). The specific relationship which the information X and the information Y need to satisfy during decryption is, for example, f(I)=true.